Walls and gates

Time: O(MxN); Space: O(G); medium

You are given a M x N 2D grid initialized with these three possible values: * -1 - A wall or an obstacle. * 0 - A gate. * INF - Infinity means an empty room.

We use the value 2^31 - 1 = 2147483647 to represent INF as you may assume
that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a Gate, that room should remain filled with INF

Have you met this question in a real interview?

Example1:

Input: rooms =

[
    [2147483647, -1,         0,          2147483647],
    [2147483647, 2147483647, 2147483647, -1],
    [2147483647, -1,         2147483647, -1],
    [0,          -1,         2147483647, 2147483647]
]

Output:

[
    [3, -1, 0,  1],
    [2,  2, 1, -1],
    [1, -1, 2, -1],
    [0, -1, 3,  4]
]

Explanation:

  • the 2D grid is:

  • INF -1 0 INF

  • INF INF INF -1

  • INF -1 INF -1

  • 0  -1 INF INF

  • the answer is:

  • 3  -1   0   1

  • 2   2   1  -1

  • 1  -1   2  -1

  • 0  -1   3   4

Example2:

Input: rooms =

[
    [0,         -1],
    [2147483647,2147483647]
]

Output:

[
    [0,-1],
    [1,2]
]

[1]:

from collections import deque

class Solution(object):
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: void Do not return anything, modify rooms in-place instead.
        """
        INF = 2147483647
        q = deque([(i, j) for i, row in enumerate(rooms) for j, r in enumerate(row) if not r])
        while q:
            (i, j) = q.popleft()
            for I, J in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
                if 0 <= I < len(rooms) and 0 <= J < len(rooms[0]) and rooms[I][J] == INF:
                    rooms[I][J] = rooms[i][j] + 1
                    q.append((I, J))
        return rooms

[2]:

s = Solution()
assert s.wallsAndGates([[2147483647, -1,         0,          2147483647],
                       [2147483647, 2147483647, 2147483647, -1],
                       [2147483647, -1,         2147483647, -1],
                       [0,          -1,         2147483647, 2147483647]
                      ]) == [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]